package other;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目： 字符流中第一个不重复的字符
 * @Author Gavin
 * @date 2022.08.06 16:29
 */
public class solution_9 {
    /**
     * 解题思路：
     *  本题涉及到的字符为都为 ASCII 码，因此使用一个大小为 128 的整型数组就能完成次数统计任务。所以使用一个字符数组来统计字符出现的次数。
     *  然后由于是数据流，也就是先进先出，所以用一个队列来存储每一个字符。
     */

    private int[] arr=new int[128];
    private Queue<Character> queue=new LinkedList<>();//注意不能使用PriorityQueue，它是优先级队列，不是先进先出的
    public void insert(char c){
        arr[c]++;
        queue.add(c);
        /**
         * 临界条件分析：
         * 1. 首先要保证队列不为空，然后判断队列的首元素在数组中下标的值是否大于1，大于1则说明重复了就出队列
         * 目的就是保证队列的第一个元素出现的次数为1
         */
        while (!queue.isEmpty()&&arr[queue.peek()]>1){
            queue.poll();
        }
    }
    public Character solution(){
        return queue.isEmpty()?'#':queue.peek();
    }
}
